package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         743,
		Discription: "需要多少时间让信号传遍每一个节点",
		Level:       2,
		Labels: map[string]int{
			"图连通性": 1,
			"拓扑排序": 1,
			"队列":   1,
			"DJ":   1,
		},
	})
}

func NetworkDelayTime(times [][]int, n int, k int) int {
	//每个边的下一个节点、以及到达下一个节点所需消耗的时间
	edges := make([][][2]int, n+1)
	for i := range times {
		edges[times[i][0]] = append(edges[times[i][0]], [2]int{times[i][1], times[i][2]})
	}

	//每个节点的最早信号到达时间，-1标识信号暂时到不了这个节点
	arrivedTimes := make([]int, n+1)
	for i := 1; i <= n; i++ {
		arrivedTimes[i] = -1
	}
	arrivedTimes[k] = 0

	//类似拓扑排序的思路遍历图
	q := [][2]int{{k, 0}}
	for len(q) != 0 {
		nodeIndex := q[0][0]
		arriveTime := q[0][1]
		q = q[1:]
		for _, edge := range edges[nodeIndex] {
			tempArrivedTime := arriveTime + edge[1]
			//如果下一个节点没被访问过，或者从当前节点到下一个节点的用时更短，就让下一个节点进队，用更短的到达时间去遍历下下个节点们
			if arrivedTimes[edge[0]] == -1 || tempArrivedTime < arrivedTimes[edge[0]] {
				arrivedTimes[edge[0]] = tempArrivedTime
				q = append(q, [2]int{edge[0], tempArrivedTime})
			}
		}
	}

	//找最晚信号到达的节点
	res := 0
	for i := 1; i <= n; i++ {
		if arrivedTimes[i] == -1 {
			return -1
		}

		res = max(res, arrivedTimes[i])
	}

	return res
}
